package cn.zifangsky.dp.questions;

import org.junit.Test;

/**
 * 无限繁殖小羊问题：
 * <p>假设农场中成熟的母牛每年只会生 1 头小母牛，并且永远不会死。第一年农场有1只成熟的母牛，从第二年开始，母牛开始生小母牛。
 * 每只小母牛3年之后成熟又可以生小母牛。给定整数N，求出N年后牛的数量。</p>
 *
 * <p><b>f(n) = f(n-1) + f(n-3)</b>，并且 f(1)=1，f(2)=2，f(3)=3</p>
 *
 * @author zifangsky
 * @date 2020/5/25
 * @since 1.0.0
 */
public class Problem_004_BreedLamb {

    /**
     * 测试代码
     */
    @Test
    public void testMethods(){
        int n = 6;

        //1. 测试方法一
        System.out.println(solution1(n));
        //2. 测试方法二
        System.out.println(solution2(n));
    }


    /**
     * 解法一：根据公式<b> f(n) = f(n-1) + f(n-3) </b>，使用暴力递归方式求解
     *
     * @param n 第 N 项
     */
    private int solution1(int n){
        if(n < 1){
            return 0;
        }

        if(n == 1 || n == 2 || n == 3){
            return n;
        }

        return solution1(n - 1) + solution1(n - 3);
    }

    /**
     * 解法二：根据公式<b> f(n) = f(n-1) + f(n-3) </b>，从左到右把数列的每一项值都求解出来
     *
     * @param n 第 N 项
     */
    private int solution2(int n){
        if(n < 1){
            return 0;
        }

        if(n == 1 || n == 2 || n == 3){
            return n;
        }

        //默认为第3项
        int result = 3;
        //默认为第2项
        int pre = 2;
        //默认为第1项
        int prepre = 1;
        int tmp1 = 0;
        int tmp2 = 0;

        for(int i = 4; i <= n; i++){
            tmp1 = result;
            tmp2 = pre;
            result = result + prepre;
            pre = tmp1;
            prepre = tmp2;
        }

        return result;
    }


}
